package com.work.interview;

/**
 * 升序数组查找数组中绝对值最小的值
 * 不允许O（N） 遍历
 * Created by suk on 2020/8/26.
 */
public class XiaoMi_0826 {
    public static void main(String[] args) {
        int[] nums = {-1, 2, 3, 7};
        System.out.println(abs(nums));
    }

    private static int abs(int[] nums) {
        /**
         * 都为负或者都为正的处理
         */
        if (nums[0] >= 0)
            return nums[0];
        if (nums[nums.length - 1] < 0)
            return nums[nums.length - 1];

        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {

            int middle = left + (right - left) / 2;

            if (nums[middle] == 0)
                return 0;

            // 如果中间是正数,则右边一定大于等于该数.再往左边查找.
            if (nums[middle] > 0) {
                if (nums[middle - 1] <= 0)
                    return Math.min(Math.abs(nums[middle - 1]), nums[middle]);
                right = middle - 1;
            } else {
                if (nums[middle + 1] > 0)
                    return Math.min(Math.abs(nums[middle]), nums[middle + 1]);
                left = middle + 1;
            }
        }

        return nums[right];
    }
}
